On the Internet, electronic messages passed between two communicating parties are typically routed by various intermediate nodes. Although the communicating parties usually identify themselves to one another, they often do not desire to reveal to others on the network the contents of their communications. To that end, measures employing encryption methods can be used to prevent eavesdropping. Moreover, in some cases, the fact that a certain client is communicating with a particular Web host alone can be considered sensitive information. In other words, the parties do not want others to know who is talking to whom. For instance, a user may want to access a Website that provides information of a sensitive nature but does not want other people to find out that she has visited that Website. To protect the anonymity and privacy of the client in terms of the client-server association, mechanisms that defeat potential traffic analyses need to be deployed.
In the literature, there have been two approaches to providing private or anonymous communications over the Internet or a similar large network. The first approach is referred to as the “mix-style” anonymity. Under this approach, a chain of pre-selected intermediate nodes, called “mixes,” are inserted between a client application (e.g., a Web browser) and a target server (e.g., a Web host) for masking the existence of the client-server communications. To protect the contents of the communications, messages sent out by the client or the server are encrypted with a key shared by the client and the server. In addition, to prevent the first and last mixes on the routing chain from comparing the encrypted messages going through them and finding out that they are on the same chain, a scheme called “onion encryption” is used to make the messages appear differently on each intermediate link of the chain. The onion encryption scheme involves multi-layered encryption and decryption operations. The client encrypts each message to be sent to the target server multiple times with different keys, one for each mix in the routing chain, in the order of the mixes in the chain. When the message is routed through the chain, each mix “peels off a layer of the onion” by decrypting the message with its key, and forwards the decrypted message to the next mix on the chain. Due to the use of the onion encryption scheme, the “mix-style” approach is often referred to as “onion routing.”
Thus, the “mix-style” approach hides, or “masquerades,” the client-server association by mixing the client-server messages with other traffic flows routed by the mixes, and constantly changing the appearance of the messages along the way, to make it difficult to trace the traffic from the client to the server and vice versa. For this scheme to be effective, a large number of client applications are required to send messages through the same set of mixes so that the mixes can batch, delay, reorder, and pad the messages to confuse anyone who tries to analyze the traffic to find out which outgoing message from a given mix corresponds to which message that came to the mix. In the case that there is not enough client traffic that can be manipulated to cause confusion, the mixes will generate fake traffic called “cover traffic” to enhance the masquerading effect.
Although the mix-style approach is quite effective, a main drawback of that approach is its inefficiency and high implementation cost. The expenses of generating cover traffic, the centralization and delay required to ensure the accumulation of sufficient genuine traffic to obscure sender/receiver correlations, and the need for costly synchronization of message processing for avoiding timing attacks make the deployment of mix-style networks somewhat impractical. Furthermore, any weakening of these expensive masquerading measures opens the door to potentially devastating attacks. Such attacks are typically fairly easy for the first and last nodes on a given routing chain to carry out just by communicating and correlating (and possibly altering) the traffic that passes through them.
The second approach proposed for hiding the client-server association is based on the “crowds-style” anonymity scheme. Under this approach, browsers on client machines can “join the crowds” and become candidates for routing traffic from and to other browsers. In other words, the client browser not only sends its own requests to a target Web host but also routes Web requests and responses for other clients. The efficacy of privacy protection provided by this scheme relies on the large number of browser routers in the “crowd.” The main source of security lies in the fact that any browser on the forwarding chain could be the initiator of the forwarded request. Thus, the real client that sends the requests to the target server has “plausible deniability,” in the sense that it can assert the requests were initiated by another client machine, and it is just forwarding those requests.
A significant drawback of the “crowds-style” approach is that there cannot be a firewall between browser routers. This limitation can severely compromise the security of the client systems participating in the scheme. Moreover, each browser on the chain needs to see the plaintext request in case it decides to forward it directly. As a result, every browser in the chain knows the target server. The first browser, which is connected directly to the client and sees both ends of the chain clearly, may then be able to deduce from the timing, context, or external information of the messages that it is indeed the first node on the chain, thereby discovering the client-server association.
In view of the foregoing, what is needed is a new and improved privacy/anonymity protection scheme for communications over the Internet (or similar large networks) that has the general advantages of the “mix-style” and “crowds-style” approaches discussed above but avoids the drawbacks associated with those approaches.